A random process can be defined on the set of states of a finite state machine. A corresponding sequence of random state transitions can be visualised as a path on a trellis diagram. The problem of finding the most probable trellis path which connects two given states is of a great practical importance. This problem arises in such diverse areas as the theory of error-free communication, adaptive planning, the theory of traffic flows. In applications related to communication theories, most probable path-searching algorithms are used to reduce noise from signals transmitted over noisy channels (CDMA2000, Gigabit internet, etc), combat both inter symbol interference and channel noise in magnetic and optical storage devices, maintain communications with deep space research probes (e.g. Galileo).
Markov processes with Gaussian randomness are of particular practical importance, one example of which is an additive Gaussian white noise (AWGN) communication channel. In such a Markov process, the problem of finding the most probable path reduces to the problem of finding the path of lowest weighting on a trellis, whose branches are equipped with weightings which are real numbers called branch metrics.
This type of problem can be solved by techniques of maximum likelihood detection. Maximum likelihood detection may include detection of transmitted data and estimation of transmitted symbols which formed part of the data before the effect of noise and/or interference during transmission. Maximum likelihood detection may also include the further step of decoding the data from an encoded format, although this is not an essential feature of a maximum likelihood detector.
In the following discussion, the term “detection” includes the process of recovering signals that are subject to noise and/or known interference, such as inter-symbol interference (ISI) of a known shape. However, if a deliberate encoding process has also been performed on the data, “decoding” is required to recover the signals in their pre-encoded form. For example, if encoding has been performed on purpose to increase resistance of the transmitted signals to noise, then “decoding” can be used to obtain the original pre-encoded signals.
It follows that a “detector” does not require any decoding means for decoding from a deliberate encoding process. However, a detector which includes such decoding means for decoding from a deliberate encoding process may be known as a “decoder”. The decoding means may be configured to work separately or integrally with the detection means. Thus, in the following discussion, a “decoder” is a type of detector which also performs decoding. The hard disk drive examples discussed below are maximum likelihood “detectors”, because the process involved is recovery of signals, where no purposeful encoding was performed on the data. However, everything that is discussed below is also applicable to decoders.
Both detectors and decoders usually output an estimate of a signal before encoding or interference. However, it is possible for a decoder or a detector to output a different sequence, e.g. outputting encoded signals which are corrected for interference and/or noise, or correcting for transmission noise but not correcting for inter-symbol interference.
An example of a maximum likelihood detector (MLD) is a convolution detector, for detecting and decoding data in a convolution encoded format. Convolution encoding is a bit level encoding technique where each coded bit is generated by convolving the input bit with the past input bits. This can be done by temporarily storing past input bits in delay elements such as flip flops or other memory or storage elements. Thus the information content of each input bit is spread over a number of coded bits, improving the error resistance of the data. If the encoded bits are then transmitted through a noisy environment, and if a particular encoded bit is very strongly affected by noise, information relating to the original input bits is still preserved in the encoded bits which are less affected by noise. The constraint length K of the convolution encoder is the number of bit shifts over which a single input bit can influence the encoder output.
A further example of convolution encoding occurs in a hard disk read system. Each bit on the disk surface generates a magnetic field, which is detected by the disk read head in order to read the bit. However, the read operation is also affected by the magnetic field produced by the neighbouring bits. Thus, any data value obtained in a read operation actually corresponds to a convolution of magnetically recorded bits on the disc. This is known as inter symbol interference (ISI).
Convolution encoders can be classified according to their constraint length, and the weightings given to each previous bit. One type of convolution detector is known as “PR4” (partial response system of class IV). “Partial response” refers to the fact that several input bits each give a partial contribution to each output bit of a multi-bit detected sequence. A more complex example is an “E2PR4” detector, which has a constraint length of five. E2PR4 detectors are commonly used in modern hard disk read channels.
A convolution encoder may be modelled by a generator polynomial G(D), which describes the number of bits influencing the encoder output, and the magnitude of each bit's influence. The generator polynomial has the formula:
      G    ⁡          (      D      )        =            ∑              n        =        0                    K        -        1              ⁢                  g        n            ⁢              D        n            where Dn is a delay operator representing a delay of n time units, K is the encoder constraint length and gn's are real numbers, which describe the weight with which past transitions contribute to the current reading. An example of a PR4 encoder has a generator polynomial of 1−D2, and an example of an E2PR4 encoder has a generator polynomial of 1+2D−2D3−D4.
A simpler example of a convolution encoder has a generator polynomial G(D)=1−D. This encoder has a single delay element for storing a previous input, and produces an output equal to the current input minus the previous input. Thus, the encoder operates on the input data xi to give an output of G(D)xi=xi−Dxi. The delay operator acts to represent the previous (delayed) input, thus Dxi=xi−1, and G(D)xi=xi−xi−1. The constraint length is 2 because each input bit influences the output over two bit shifts.
FIG. 1 shows a block diagram of a prior art apparatus for transmission and reception of convolution encoded data. The apparatus includes a convolution encoder 100, with generator polynomial G(D)=1−D. The apparatus of FIG. 1 may represent a communications system, with deliberate convolution encoding of data to increase noise resistance during transmission through a channel. However, it may also represent a hard disk read process, in which the convolution encoding is not deliberate, but is a result of inter symbol interference caused by the magnetic fields of the individual data bits on the disk.
The encoder 100 performs convolution encoding of a stream of input data. The data is then sent over a noisy channel. Noise source 104 represents the effect of noise during transmission of the data. The transmitted data is then received and decoded by a detector 108.
The encoder 100 has an input 101 for accepting a stream of time dependent input binary data xi, where i represents the time interval. The input data is received by the encoder at a rate of k bits/second. The input 101 of the encoder 100 is connected to an encoder delay element 102. The delay element 102 stores a single bit of data, corresponding to the input bit xi at time i, and outputs this data bit at the following time interval i+1. Thus, at time i, the output of the delay element is xi−1. The output of the delay element 102 is connected to a multiplication unit 103 which multiplies the output value xi−1, by minus one, giving an output of −xi−1. The encoder 100 has a sum unit 104 which is connected to both the encoder input 101 and the output of the multiplication unit 103. The signals xi and −xi−1, are summed by the sum unit 104, to give an output signal of yi=xi−xi−1.
The encoder output signal yi is sent from the output 105 of the encoder 100 via a channel, such as a radio link, a wire, or any other form of data transmission channel, to a detector 108. Noise source 106 represents noise ni generated as the signal yi passes through the channel. This may be any type of noise, for example, decorrelated noise such as white noise or Gaussian white noise. A sum unit 107, with inputs connected to the noise source 106 and the encoder output 105, represents the addition of the noise ni to the data yi. Thus, the signal received after the data has passed through the noisy channel is ri=yi+ni. The detector 108 receives the signal ri, and the detector then performs a detection and convolution decoding process.
A prior art method of detection or detection and decoding of convolution encoded data uses a technique known as the Viterbi algorithm (VA). VA is a recursive procedure, which can be most easily described when used with a known initial state at time t=0, and a known final state at time t=T. VA allows the most likely sequence of states at intermediate times to be found. FIG. 2A shows an example of a two-state trellis diagram which can be used to visualise the VA process. The trellis diagram is a state transition diagram which graphically represents all of the possible states of the system over a sequence of time intervals. The horizontal axis of the trellis represents time, starting at time t=0 at the left hand side of the trellis, and ending with time t=T at the right hand side of the trellis. The vertical axis represents the possible states of the finite state machine. In this example, these possible states are zero and one, corresponding to the possible input states xi of the convolution encoder of FIG. 1. Pairs of possible states at adjacent time intervals are connected by lines, with each line representing a state transition to a different state or to an identical state during one time interval. The possible sequences of states over the whole of the time period are represented by the possible paths along the trellis. At time t=0, the system is pre-set to state zero. At the next time interval, t=1, the state may remain as zero or change to one. This is represented by the darker upper and lower lines of the trellis between t=0 and t=1. A change of state from zero to one is represented by the upper line, extending diagonally upwards to connect to one, and a sequence of all zero states is represented by the lower line, extending horizontally to connect to zero. At time t=1, if the system is in state one, it may follow one of two routes, i.e. remain at one, or change to zero. Similarly, if the system is in state zero, it may follow one of a further two routes, i.e. remain at zero, or change to one. At the final time t=T of the trellis of FIG. 2A, the system is reset to zero, thus only state zero is a possible state.
As can be seen from FIG. 2A, the trellis contains one or more paths between each possible initial and final state. For instance, there are two different paths from the “zero” state at time t=0 to the “zero” state at t=2. These paths are 010 and 000, where the first bit represents the state at time t=0, the second bit represents the state at time t=1, and the third bit represents the state at time t=2. FIG. 2B shows an identical trellis to FIG. 2A, with these two paths in bold lines. VA involves identifying paths between any possible states at time t−1, and each possible state at time t. If more than one path connects from t−1 to a particular state at time t, then VA chooses which of these paths corresponds to the most likely state sequence. Then, the least likely paths are eliminated. The remaining path is called the survivor.
The most likely path through the trellis can be determined using numbers known as branch metrics, which indicate the relative likelihoods of each of the possible state transitions in the trellis occurring. The branch metrics for each time interval may depend on the previous encoder state, and the new encoder input. The number shown beside each line in the trellis in FIGS. 2A and “B are the branch metrics. In one example, relating to FIG. 1, branch metrics may be obtained using the expected values yi of the received data ri and the actual values ri of the received data. The branch metrics in a path from time t1, to time t2 can be summed to indicate the likelihood of that path occurring. These sums of branch metrics are known as path metrics.
To find a survivor at a given state at t=t+1, the path metrics of all paths leading to this state are computed by adding appropriate branch metrics to path metrics of survivors at time t and choosing the path of lowest path metric (i.e. the highest likelihood path) leading to this state. This procedure is called add-compare-select operation and it has to be performed for all states at t=t+1. As t=T is reached, there will be only one survivor left, with probability P=1−C1·exp(−C2·T), where C1 and C2 are constants. Thus, the probability P approaches 1 as time T increases and C1·exp(−C2·T) becomes small.
VA is capable of reducing the amount of de-correlated noise, such as Gaussian white noise, from received data. VA may also be used to reduce the amount of coloured noise, if the correlation length of the noise is small enough.
FIG. 3 illustrates the use of VA by the detector 108 of FIG. 1, to detect the received data ri, and output a corresponding sequence of values indicating the estimated encoder input values of highest likelihood. A series of eight trellis diagrams are shown, representing eight steps of the VA decoding process. A ninth trellis diagram shows a trace-back of the optimal path through the trellis. Again, the numbers on the trellis diagrams represent branch metrics, indicating the likelihood that received data corresponds to particular state transitions. Each trellis diagram is similar to that described with reference to FIGS. 2A and 2B, i.e. it has two possible states which are one and zero. These also represent the possible values of xi−1, which are sequentially stored in the delay element 101.
The trellis extends from a known state of zero at time t=0 to a known state of zero at time t=T. A path through the trellis represents a sequence of data which is input to the encoder. Any unique data sequence input to the encoder has a unique path through the trellis. The initial state of each trellis is set to zero, by pre-setting the delay element to zero, i.e. setting the first value of xi to zero. The information which is to be convolution encoded and transmitted then begins with the second value of xi. At the end of the information, an extra zero character is added to allow the last character of the information to be fully convolution encoded. It is not essential that this initial and final state should be zero, but in this example, their values should be known by the detector.
The states of the trellis, with a value of zero or one, represent possible values of xi−1, where xi−1 is a possible value of the convolution encoder input, which is stored in the delay element 102. The possible values of the convolution encoder output, yi=xi−xi−1, are thus represented by the slope of the lines connecting two states of the trellis at adjacent time intervals i−1 and i. The values of yi are known as “branch labels”, and they represent ideal values of the received data, without any added noise ni. Lines with a zero slope, (such as the line between state zero at t=0 and state zero at t=1) correspond to yi=0. Lines with a left-to-right upwards slope (such as the line between state zero at t=0 and state one at t=1) correspond to yi=1. Lines with a left-to-right downwards slope (such as the line between state one at t=1 and state zero at t=2) correspond to yi=−1.
When the detector receives the transmitted signal, this signal ri may include noise ni. Thus, the problem to be solved by the detector is to determine the most likely path through the trellis (i.e. the most likely sequence of characters input to the encoder), based on the noisy received signal. The branch metrics are assigned to the trellis to indicate the likelihood of each state corresponding to the received signal at that time. For additive Gaussian white noise (AGWN), the branch metrics can be calculated as (ri−yi)2, i.e. the square of the difference between the received value ri and the expected value yi at that point in the trellis. The most likely path is the path with the lowest path metric.
When the formula (ri−yi)2 is used to calculate branch metrics for the two-state trellis of FIG. 3, it is common to get a lot of different paths having equal path metrics. It may not always be possible, therefore, to choose a single path of greatest likelihood, because one of two equally likely paths must be chosen. Therefore, for the purposes of illustrating the technique of finding a unique path through the trellis using VA, the values shown on FIG. 3 as branch metrics have not been calculated from a sample set of received data ri, but instead, small integers have been chosen for each branch metric to ensure different weights for each path.
In practice, although the presence of multiple paths of equal likeliness degrades the VA performance, it is often possible to pre-process the data to avoid getting large numbers of equally likely paths.
The first trellis diagram, at the top of FIG. 3, corresponds to step 1 of the detection and/or decoding process. Step 1 concerns the time interval between t=0 and t=1. The state of the system at t=0 is zero, because the delay element was preset to zero before data transmission began. Two possible paths through the trellis during the first time interval are identified as bold lines on the trellis. These correspond to data sequences of 00 and 01 respectively, where the first bit represents the state at time t=0 and the second bit represents the state at time t=1. The 00 path is the lower of the two paths in the trellis, and the 01 path is the upper of the two paths in the trellis. The 00 path has a path metric of 0, but the 01 path has a path metric of 2. As only a single path is formed between the initial state at time t=0 and the next state at t=1, no reduction of the trellis is performed at step 1.
The second trellis corresponds to step 2 of the decoding process. The part of the trellis between t=0 and t=2 is now considered. A total of four paths are now possible, namely, 000, 001, 010 and 011, where the first two bits represent the possible paths in step 1, and the third bit represents the state at time t=2. The path metric of each path may be calculated by adding all the branch metrics on the path. Thus, the path metric of 000 is 0+2=2, of 001 is 0+0=0, of 010 is 2+1=3, and of 011 is 2+1=3. The paths 000 and 010, with path metrics of 2 and 3 respectively, both lead to a final state of 0 at time t=2. Therefore, the 010 can be eliminated, as it has the highest path metric, and the 000 path is the survivor. Similarly, the paths 001 and 011, with path metrics of 0 and 3 respectively, both lead to a final state of 1 at time t=2. Thus, the 011 path can be discarded, and the 001 path is the survivor. The two survivor paths, 001 and 000, are shown in bold on the trellis diagram.
In step 3 of the process, the part of the trellis up to t=3 is considered. The four new possible paths are 0010, 0011, 0000 and 0001, with path metrics of 0, 0, 3 and 4 respectively. The paths 0000, with path metric 3, and the path 0001, with path metric 4, can both be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 0010 and 0011, each with a path metric of 0.
In step 4 of the process, the part of the trellis up to t=4 is considered. The four new possible paths are 00100, 00101, 00110 and 00111, with path metrics of 1, 2, 2 and 0 respectively. The paths 00101 and 00110 can be eliminated, as these have highest path metrics for final states 1 and 0 respectively. Thus, the survivors are 00100 and 00111, each with a path metric of 0.
In step 5 of the process, the part of the trellis up to t=5 is considered. The four new possible paths are 001000, 001001, 001110 and 001111, with path metrics of 3, 3, 1 and 0 respectively. The paths 001000 and 001001 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 001110 and 001111, with path metrics of 1 and 0 respectively.
In step 6 of the process, the part of the trellis up to t=6 is considered. The four new possible paths are 0011100, 0011101, 0011110 and 0011111, with path metrics of 3, 2, 2 and 1 respectively. The paths 0011100 and 0011101 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 0011110 and 0011111, with path metrics of 2 and 1 respectively.
In step 7 of the process, the part of the trellis up to t=7 is considered. The four new possible paths are 00111100, 00111101, 00111110 and 00111111, with path metrics of 2, 4, 3 and 3 respectively. The paths 00111110 and 00111101 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 00111100 and 00111111, with path metrics of 2 and 3 respectively.
In step 8 of the process, the part of the trellis up to t=8 is considered. At t=8, the state is set to zero, since a reset signal will be sent at the end of each transmission. Thus, there are only have two paths to consider instead of four. The two paths are 001111000, 001111110, with path metrics of 2 and 4 respectively. As both paths have the same final state, the path 001111110, which has the highest path metric, can be eliminated. Thus, the only survivor is 001111000, with a path metric of 2.
The ninth trellis shows trace-back of the path with the lowest overall path metric, where only the final survivor path is shown in bold, and dead-end paths are no longer shown in bold.
In the absence of any additional noise ni, the received data input to the detector or decoder is an “ideal input”. For a trellis of finite length, an ideal input is a sequence of received data with a corresponding path in the trellis which has a path metric of zero. In other words, for an ideal input, there is a corresponding path which has a sequence of branch labels which is equal to the sequence of received data.
High speed implementations of maximal likelihood detectors (MLDs) such as the above (1−D) example, PR4 detectors and E2PR4 detectors, rely on a simultaneous computation of a large number of branch metrics of length n, where n is the number of time steps of the trellis processed in parallel. Such detector designs are referred to as radix-2n designs. It is often convenient to choose n to be equal to the constraint length of the detector. The constraint length is the smallest number of time steps on the trellis for which loops, i.e. multiple paths connecting a given state at time T to a given state at time (T+n), appear. For example, E2PR4 has a constraint length of 5, thus the length of branch metrics for minimum loop size is 5, and the radix of corresponding designs is 25=32. The calculation of a large number of branch metrics is both time and area consuming, and this is a limiting factor in a high speed MLD design.
An increase in the detector's throughput can be achieved by increasing its radix. However, the area penalty for such increase can be significant. For example, radix-32 implementation of a “sliding-window” type E2PR4 MLD requires the computation of branch metrics for paths connecting each of 16 initial states to each of 16 final states, where two paths are obtained for each connection. This is 512 different paths on the corresponding trellis. If this computation is performed in 512 independent blocks, the total area of the branch metric block alone will be approximately 512×10000 μm2≈5 mm2. In comparison, the total area of currently used high speed radix-4 detectors is approximately 0.6 mm2.